\documentclass[11pt]{beamer}
\usepackage[UTF8,scheme=plain]{ctex}
\usepackage{listings}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usetheme{Boadilla}


\lstset{
	basicstyle=\footnotesize,
    flexiblecolumns,
    showstringspaces = false,
	numbers=left,
    numberstyle=\tiny,
    numbersep=5pt,
	breaklines,%自动换行
	frame=shadowbox,%加边框
	backgroundcolor = \color{red!30!green!30!blue!30},
	%背景色：蓝灰色
	language=C++, % 语言为 c++
	commentstyle=\color{red!80!green!80!blue!80},% 注释用蓝灰色字体标出
	keywordstyle=\color{blue!70}, % 高亮部分用蓝色字体
	tabsize = 4
}

\begin{document}
	\author{ 路毅 \hspace{0.3cm} 曲阜师范大学 }
	\date{\number\year 年 \number\month 月 \number\day 日}
	\title{计算物理第１部分}
    \subtitle{前言、计算语言与工具、数值误差}
	%\subtitle{}
	%\logo{}
	%\institute{}
	%\date{}
	%\subject{}
	%\setbeamercovered{transparent}
	%\setbeamertemplate{navigation symbols}{}
	\begin{frame}[plain]
	\maketitle
\end{frame}

\kaishu

\begin{frame}
\frametitle{目录}
	\begin{itemize}
		\item {\color{blue} 第一章：前言 \hspace{0.2cm} }
		\vspace{1cm}
		\item 第二章：计算语言、工具与误差
		\vspace{1cm}
		\item 第三章：数值误差
	\end{itemize}
\end{frame}

\begin{frame}
\frametitle{为什么要学计算物理}
\begin{itemize}
	\item  理论、计算、实验 三足鼎立。
	\item 科学计算在生活中变得越来越重要(大数据、机器学习。。。)，所以了解一点计算的思维方式是很好的。
	\item 重现、预测客观世界的雄心壮志。
	
	不管是遥远天穹中的恒星，还是最小尺度下的夸克，只要我们能想象到的东西，我们都要用代码模拟和计算他们，预测他们。
	\item 有趣好玩(智力乐趣)
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{编程语言}
\begin{itemize}
	\item {\bf \color{red} c/c++} \hspace{2cm} %$\surd$
	\item fortran
	\item mathematica
	\item matlab
	\item maple
	\item python
	\item else
\end{itemize}

还有很多语言正在出生和死亡，像天上的恒星，沿着时间的单箭头演化。

\end{frame}

\begin{frame}
\frametitle{为什么选 c++}

\begin{itemize}
	\item c/c++ 和 fortran 代码在现有科学程序中较多
	\item 本科阶段，大家都学过 c，有一点印象。%c++ 与 c 很相似，c++ 扩展了类、面向对象等内容，但我们这门课只用到函数式编程，所以 c/c++ 对我们来说几乎是一样的。也就是说，你用 c 的习惯做作业，一样能编译通过运行。
	%\item mathematica/matlab/maple/python 有很多库函数可以调用，你也可以找一本使用手册，查查怎么调用那些库函数，来实现一些特定的功能。但是你不知道为什么那些库函数管用，也不知道什么时候不管用。尤其是，如果你的需求和这些函数有些不一样，你就没法指望上它们。。。
	\item 教师路毅对C++更熟悉。
     %计算物理要教给大家的，是怎样分析和理解常用的算法，并进行相关的物理应用。我们希望你学了这门课以后，能自己动手，为自己的需求量身编写代码，并能对代码的性能、资源需求进行评估。你是自由的。
\end{itemize}

\end{frame}

\begin{frame}
\frametitle{关于编程}

\begin{itemize}
	
	\item {\bf 静}：静下心来花时间，写清晰。
	
	\item {\bf 恒}：程序编译不通过，需要恒心，找到每一个bug。
	
	\item {\bf 喜}：编译通过，输出正确结果的时刻，会有喜悦和成就感。
	
	\item {\bf 乐}：学会搜索查阅资料，实现自己想要的功能。比如：
	               \begin{itemize}
	               \item 学习 openmp 和 openmpi， 调用电脑的所有内核，进行并行计算。
                   \item 学习 latex，习惯写latex代码，写笔记、论文更便捷。
	               \item 学习 gnuplot， 让电脑自动画图，生成 latex 编码，自动生成图文并茂的 pdf 文件。全自动，你值得拥有。
	               \item 你可以通过几行命令，让linux系统定期给好友发送“生日快乐”的邮件。。。也许还是个谈恋爱的攻略。。。
                   \end{itemize}
                    能自主学习，就是一种独立。
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{关于编程的小建议}

	\begin{itemize}
	\item {\bf 写程序之前，尽量搞清楚一个算法，以及程序的算法、数据流程。}
	%我自己犯过这个错误不止一次，如果没有完全搞清楚算法，写到一半的时候，可能会发现行不通，或者前面写的都要改，那就很头疼了。。。
	\item {\bf 写程序要注意层次(缩进)，多写注释和文档。}
	%层次主要是靠缩进体现的，如果没有层次，没有注释，可能过两周，就会感到茫然，并拷问自己的灵魂：“我都写了些什么？”
	%最好是注意层次（缩进），并在程序中稍微多写一点注释，并且在程序开头，或者同一个文件夹中的"ReadMe"文件中写下程序的使用方法，甚至加上使用例子。
	%这样，下次使用时，你会非常感激两周前的自己。
	\item{\bf 变量名、函数名尽量用有意义的名字}\\
	如果你的变量名叫做 $x1, x2, x3$，分别代表温度、气压、玻尔兹曼常数等等，你很可能会犯错误，而且难以找到错误。。。
	不如叫做 T, P, kb，这样来的实在。
    
    \item 推荐参考书：《Clean Code: A Handbook of Agile Software Craftsmanship》
\end{itemize}
\end{frame}

\begin{frame}{课程预备知识}
\begin{itemize}
	\item 本课程预期同学们熟悉高等数学、线性代数、概率论、C/C++语言。
	%\item 我预期同学们修过 c 或者 c++，但我不做很多指望，我们会回顾 c++ 的最基本内容。
	%\item 不做要求，但是如果熟悉我们计算的一些物理系统，会很有帮助。\\
	\item {\bf (不要求)《量子力学》}：我们将会求解一些简单的量子系统，包括谐振子、氢原子，如果还记得一些《量子力学》会更有感觉。
	\item {\bf (不要求) 《热力学与数理统计》}：我们会讲解最简单的统计模型：Ising 模型，并用 Monte Carlo 方法模拟这个模型，如果还记得一点《热力学与数理统计》中的正则分布，会更理解这些技巧的目的。。。
	\item {\bf (不要求)《力学》《数学物理方法》} 我们会求解单摆、受迫振动，也许会讲解，怎样用数值的格林函数法求解微分方程，也可能编写一点特殊函数，所以熟悉《数学物理方法》中的内容，会很得心应手。
	
	%\item 如果完全不记得，讲到的时候再把那些书翻一翻，也会有助于理解。
\end{itemize}

\end{frame}

\begin{frame}{课程内容}
课程内容分为以下几部分，每个部分包括几章内容
\begin{itemize}
	\item [1] c++ 以及一些计算工具的介绍
	\item [2] 常用数值技巧：函数极值、微分、积分、方程求根、拟合与插值等
	\item [3] 微分方程：常微分方程、偏微分方程的一系列数值解法
	\item [4] 数值线性代数：线性方程组、矩阵变换、以及本征值系统
	\item [5] 蒙特卡洛方法
\end{itemize}
%我们可能略过上面列出的少量内容，也可能增添一点内容。。。\\
\vspace{1cm}
教材：Morten Hjorth-Jensen, "Computational Physics, Lecture notes" 
\end{frame}

\begin{frame}{考评方法}
总成绩 = 平时成绩 x 0.3 + 分组大作业 x 0.1 + 考勤 x 0.1 + 期末成绩 x 0.5

课程邮箱：%QFNU\_Comp\_Phys@163.com % paswd: zhang1026!
574979040@qq.com

平时每1-2周布置一次作业，需要编写程序，并在指定期限内向课程邮箱提交作业，由任课老师批改，并回复邮件。

平时作业有如下相关政策
\begin{itemize}
    %\item 指定的一个周一下午2:30之前，提交布置的作业。
	\item 超过期限的作业，将不予批阅。
	%\item 同一次作业可以提交多份，我们只批改指定期限前提交的最后一份。
	\item 如果平时成绩缺 1/3 以上，取消期末考试资格。
	\item 如果有一次平时作业确认为抄袭，取消期末考试资格。
\end{itemize}
根据前面三届的数据，期末考试的成绩与平时成绩的得分正相关。

%期末考试将采取现场编程的考试方式。

\end{frame}

\begin{frame}{平时作业要求：说明文字}

\begin{itemize}
	\item [1] 要求每份作业中都有简要的文字说明：这个程序是做什么的、怎样跑这个程序、预期得到什么样的结果
	\item [2] 可以提交不成功的代码，需要相应地说明可能存在的问题。
	\item [3] 如果没有说明文档，并且程序可读性差，而且还有bug，老师可以不予批改。
\end{itemize}
%这个说明可以作为注释，写在代码文件的开头，也可以作为一个独立 txt 文件交上来。

\end{frame}

\begin{frame}{计算的智慧}

%什么样的智慧，是属于计算这一种工作的？

\begin{itemize}

%\item 显然，计算不是为了显摆我会编程，写几千行代码，也不是最值得夸耀的事。。。
%\item 计算也不仅是为了体验工具带来的快感，虽然好机器使我们有快感，但每天产生一百万个陌生的数字、让机器嗡嗡叫，未必使我们幸福。。。

%\item 真正使人了不起的，是人的洞察力。。。\\

\item {\bf 定律由数字体现}：“纸上得来终觉浅，绝知此事要躬行”。

%\item {\bf 预言由数字给出}：

\item {\bf 算法的妙用}：我们可能会理解，一个算法巧妙在哪里，适用于什么样的问题。
碰到物理问题时，我们会饶有兴致地想到，一种算法的恰如其分的应用。

\item {\bf 洞察$>>$数字}：
上天赋予人类的最美妙礼物，不是超级计算机，或者量子计算机，而是洞察力。
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{目录}
\begin{itemize}
	\item { 第一章：前言 \hspace{0.2cm} }
	\vspace{1cm}
	\item { \color{blue} 第二章：计算语言、工具与误差 }
	\vspace{1cm}
	\item 第三章：数值误差
\end{itemize}
\end{frame}

\begin{frame}{安装 Dev C++}
\begin{itemize}
	\item 下载 Dev C++ 安装文件，我们附上下载地址\footnote{https://sourceforge.net/projects/dev-cpp/}。
	\item 下载完成以后，一般双击这个文件即可，但有时可能需要管理员权限，则右键这个文件，然后选择以管理员权限运行。
	\item 点击两三次 "OK" 或者 “下一步”即可完成安装。
	\item 建立新文件：File -> New -> Source File，然后编写程序，并保存为你指定的文件名。
	\item 编译：Execute -> Compile，或者快捷键 F9，界面下方会显示编译结果，包括错误的个数，警告的个数（警告的内容不一定是错误的，有可能只是编译器疑惑了）。
	\item 运行：Execute -> Run, 或者快捷键 F10，也可以用“编译\&运行”，快捷键为 F11。
\end{itemize}
\end{frame}

\begin{frame}[fragile]
\frametitle{Hello world}
下面是最简单的 c++ 程序 Hello world
\begin{lstlisting}
#include<iostream>   // 包括标准输入输出库
using namespace std; // 用命名空间
// 如果不写这一行，我们想用输入输出命令，就不能只打 cin, cout，而要写 std::cin, std::cout

int main(){
//主函数，包括函数返回类型（int)，主函数名（main），参数（无参数），和函数体（花括号内的内容）
    cout<<"Hello world!"<<endl;
//输出“Hello world!"这些字符。endl 是换行。
    return 0;
//主函数返回值为0，表示正常结束。你可以试试改成-1，然后看看运行结果。
}
\end{lstlisting}
\end{frame}

\iffalse
\begin{frame}[fragile]
\frametitle{Hello world}
在 Dev-C++ 中新建文件，编写好上面的程序以后，就可以用界面上的快捷键编译，运行。
如果窗口一闪而过，可以在 return 0; 的前面加一行 system("pause")，让程序在 return 0 之前暂停。
\begin{lstlisting}
#include<iostream>   
using namespace std; 

int main(){
    cout<<"Hello world!"<<endl;
    system("pause");
    return 0;
}
\end{lstlisting}
这样，你就可以看见屏幕上出现 Hello world! 的字样。
\end{frame}
\fi

\begin{frame}[fragile]{编译查错：It's human to make mistakes!}

请找出下面的代码中的错误
\begin{lstlisting}
#include<iostream>;
using namespace std

main(){
    cout<<"Hello world!"<endl;
    retrun 0;
\end{lstlisting}
\end{frame}

\begin{frame}{c++ 常用的数据类型}

所有语言的基础都是变量，只是有的需要特别声明变量的数据类型，有的不需要（比如python）。
在 c++ 中，大家经常用到的数据类型如下

\begin{table} [h]
	\centering
\begin{tabular}{|c|c|c|}
	\hline \hline
	数据类型 & 内存（byte) & 数值范围 \\
	\hline
	char	& 1			& $-128 \sim 127$ \\
	bool	& 1			& $true / false $ \\
	int		& 2 		& $-32768 \sim 32767$ \\
	long int & 4		& $-2147483648 \sim 2147483647$ \\
	float	& 4		& $10^{-44} \sim 10^{38}$ \\
	double 	& 8		& $10^{-322} \sim 10^{308}$\\
	\hline \hline
\end{tabular} 
\end{table}
byte 是 “字节”，我们平时说的 kb, mb, gb, tb 中的 b 都是指 byte。
1 个 byte = 8 个 bit，bit 是“比特”，即二进制的一位。
\end{frame}

\begin{frame}[fragile]{加法计算器}
c++ 中有加减乘除等等运算符，这些运算符有优先级规则，可以查书，也可以百度。
下面是一个简单的加法程序
\begin{lstlisting}
#include<iostream>
using namespace std;

int main(){
    int a, b, c;// 声明三个整型变量
    cout<<" Please input values of integer a and b."<<endl;// 请输入两个整数
    cin>>a;//输入 a,b 的值
    cin>>b;
    c = a + b;// c 的值为 a 和 b 的和
    cout<<" The sum is : "<<c<<endl;
    return 0;
}
\end{lstlisting}
编译通过以后运行，屏幕上会出现提示：Please input values of integer a and b.
然后输入 3，回车，5，回车，它就会告诉你：" The sum is : 8"。
这就是一个很简单的整数加法计算器了。
\end{frame}

\begin{frame}[fragile]{课堂作业：求余数}
写一个代码，要求：
\begin{itemize}
\item [1] 提示用户输入两个整数 $a,b$
\item [2] 输出$a/b$的余数(求余符号：$\%$)
\end{itemize}
\end{frame}

\begin{frame}[fragile]{数组}
如果我们需要同时操作 10 个整数，就可以定义一个 长度为 10 的数组，如下
\begin{lstlisting}
    int k[10];
\end{lstlisting}
也可以直接赋初始值 1,2，..., 10
\begin{lstlisting}
    int k[10]={1,2,3,4,5,6,7,8,9,10};
\end{lstlisting}
或用循环语句赋值
\begin{lstlisting}
    int k[100];//声明数组
    for(int i=0;i<100;i++) k[i] = i*i; // 赋值：0, 1, 4, 9, ...
\end{lstlisting}

注意，在 c/c++ 中，数组的下标是从 0 开始的，如果要改变数组 k 中的第一个数字的值，使它变为 100，应该写
\begin{lstlisting}
    k[0]=100;
\end{lstlisting}
类似地，也可以定义浮点数数组，字符数组。
\end{frame}

\begin{frame}[fragile]{数组}
下面各行相互独立，每行都有错误，请找出错误。
\begin{lstlisting}
int a=10; int k[a];
int k[3] = [1,2,3,4];
int k[10]; cin>>k;
int k[10]; int b = k[10] * 2;
int k[10]; for(int i=1;i<=10;i++)k[i]=i;
\end{lstlisting}

\end{frame}

\begin{frame}[fragile]{ if 逻辑语句}
下面我们写一个程序，输入两个双精度浮点数，让电脑告诉我们哪个更大
\begin{lstlisting}
#include<iostream>
using namespace std;

int main(){
    double a,b;
    cout<<" Please input two float numbers:"<<endl;
    cout<<"a=";
    cin>>a;
    cout<<"b=";
    cin>>b;
    if(a>b)cout<<" Conclusion: a > b "<<endl;
    else cout<<" Conclusion: a <= b "<<endl;
    return 0;
}
\end{lstlisting}
其中就用到了 if 语句。
\end{frame}

\begin{frame}[fragile]{ if 逻辑语句}

if 语句的格式是这样的
\begin{lstlisting}
    if(test){
        body1
    }
    else{
        body2
    }
\end{lstlisting}
其中 test 往往是一个逻辑语句，比如上面程序中的 a>b，那么 a>b 这个语句要么是真的，要么是假的，如果是真的，就执行 body1 中的所有语句，否则，就执行 body2 中的所有语句。
\end{frame}

\begin{frame}[fragile]{if 逻辑语句}
当然，还可以写得更复杂
\begin{lstlisting}
    if(test1){
        body1
    }
    else if(test2){
        body2
    }
    else{
        body3
    }
\end{lstlisting}
可以加上任意层的 else if，来区分各种不同的情况。

\end{frame}


\begin{frame}[fragile]{课堂作业：求余数(2)}
写一个代码，要求：
\begin{itemize}
\item [1] 提示用户这是一个求余程序，并要求输入两个整数 $a,b$
\item [2] {\color{red} 如果$b \leq 0$，提示用户，并退出程序}
\item [3] 输出$a/b$的余数(求余符号：$\%$)
\end{itemize}
\end{frame}

\begin{frame}[fragile]{for 循环语句}
大家可能都听过小学生高斯的故事，关于“高斯求和”的技巧。
我们可以写一个程序，做 1 到 100 的总和。
\begin{lstlisting}
#include<iostream>
using namespace std;

int main(){
    int i,sum=0;// 声明两个整型变量，其中 sum 的值为0
    for(i=1;i<=100;i++){
        sum += i;
    }
    cout<<" The sum of 1,2,...,100 is: "<<sum<<endl;
    // 输出结果
    return 0;
}
\end{lstlisting}
\end{frame}


\begin{frame}[fragile]{for 循环语句}
for 语句的结构是这样的：
\begin{lstlisting}
for(initial; test; increment){
    body;
}
\end{lstlisting}
其中，initial, test, increment, body 都是语句。
计算机看到 for 语句，将会做以下的事情
\begin{itemize}
	\item[1] 执行 initial，
	\item[2] 判断 test 语句是真或假
	\item[3] 如果 test 语句是真的，就执行 body 中的所有语句。然后执行 increment 语句，然后回到第 2 步。
	\item[4] 如果 test 语句是假的，就结束这段 for 语句的工作。
\end{itemize}
\end{frame}


\iffalse
\begin{frame}[fragile]{for 循环语句}
\footnotesize
\begin{lstlisting}
#include<iostream>
using namespace std;

int main(){
    int i,sum=0;// 声明两个整型变量，其中 sum 的值为0
    for(i=1;i<=100;i++){
        sum += i;
    }
    cout<<" The sum of 1,2,...,100 is: "<<sum<<endl;
    // 输出结果
    return 0;
}
\end{lstlisting}
所以上面的程序做如下事情，
\begin{itemize}
	\item[1] 在上面的程序第 6 行中，令 i=1，即赋初值。
	\item[2] 判断 i<=100 是否成立。
	\item[3] 如果成立，就执行第 7 行，让 sum 的值加上 i 的值。然后执行 i++，表示 i 的值加上 1，其值变为 2。然后回到第 2 步。
	\item[4] 如果 i<=100 不成立，就结束这段 for 语句的工作。
\end{itemize}
所以，在上面的程序中，第 7 行会被执行 100 次，这就叫做循环。
\end{frame}
\fi


\begin{frame}[fragile]{课堂作业：求余数(3)}
写一个代码，要求：
\begin{itemize}
\item [1] 提示用户这是一个求余程序，并要求输入10个被除数$ int ~~ k[10]$，与一个除数$b$
\item [2] 如果$b \leq 0$，提示用户，并退出程序
\item [3] 依次输出10个被除数的余数$ k[i] ~ \% ~ b$(求余符号：$\%$)
\end{itemize}
\end{frame}

\begin{frame}[fragile]{死循环}
如果我们将高斯求和的代码改成下面这样
\begin{lstlisting}
#include<iostream>
using namespace std;

int main(){
    int i,sum=0;// 声明两个整型变量，其中 sum 的值为0
    for(i=1;1>0;i++){
        sum += i;
    }
    cout<<" The sum of 1,2,...,100 is: "<<sum<<endl;
    // 输出结果
    return 0;
}
\end{lstlisting}
即把 test 语句写成 1>0，那么 1>0 是永远成立的，所以程序将会无限次重复步骤 2 和 3，除非系统或者人为干预，程序永远不会停下来。
这就叫做死循环。
\end{frame}

\begin{frame}[fragile]{循环语句 while}
从 1 加到 100，也可以用 while 语句写：
\begin{lstlisting}
#include<iostream>
using namespace std;

int main(){
    int i=1,sum=0;// 声明两个整型变量，其中 i 的值为1， sum 的值为0
    while(i<=100){
        sum += i;
        i++;
    }

    cout<<" The sum of 1,2,...,100 is: "<<sum<<endl;
    return 0;
}
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]{循环语句 while}
while 的结构如下
\begin{lstlisting}
while(test){
    body
}
\end{lstlisting}
其中 test 和 body 都是语句，计算机看到 while 语句，会做如下事情：
\begin{itemize}
	\item [1] 检验 test 是否为真
	\item [2] 如果 test 为真，则执行 body 中的所有语句，然后回到步骤 1
	\item [3] 如果 test 为假，则结束整个 while 语句
\end{itemize}
你可以试试，把这个 while 语句也写成死循环。
\end{frame}

\begin{frame}[fragile]{作业}

1. 试编写程序，输出1-100以内的所有质数。

2*. 编写程序，让用户给定任意两个正整数$a,b$，程序输出开区间$(a,b)$内的所有质数。

\end{frame}

\begin{frame}[fragile]{函数式编程}

我们常常需要写一些功能函数，让它们互相调用，将 main 函数作为最外层的调用。
\begin{lstlisting}
#include<iostream>
using namespace std;

void compare(int a, int b){ // 函数不返回任何值，所以类型为 void
    cout<<" Conclusion: ";
    if(a>b)cout<<a << ">" << b <<endl;
    else if(a==b)cout<<a << "=" << b <<endl;
    else cout<< a << "<" <<b <<endl;
}

int main(){
    int a,b;
    cout<<" Please input two integers:"<<endl;
    cout<<" a="; cin>>a; //在c++中，分行不影响语法。
    cout<<" b="; cin>>b;
    compare(a,b);//调用 compare 函数
    return 0;
}
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]{预先声明函数}
如果定义的函数太多，我们可能难以找到 main 函数，所以，我们可以先声明　compare 函数（c++ 要求所有函数被调用之前都被声明），然后在 main 函数的后面定义 compare 函数，如下
\begin{lstlisting}
#include<iostream>
using namespace std;

void compare(int a, int b);//声明 compare 函数

int main(){
    int a,b;
    cout<<" Please input two integers:"<<endl;
    cout<<" a=";
    cin>>a;
    cout<<" b=";
    cin>>b;
    compare(a,b);//调用 compare 函数
    return 0;
}
\end{lstlisting}
\end{frame}

%\begin{frame}[fragile]
\lstset{firstnumber = last}
\begin{lstlisting}
void compare(int a, int b){ // 函数不返回任何值，所以类型为 void
    cout<<" Conclusion: ";
    if(a>b)cout<<a << ">" << b <<endl;
    else if(a==b)cout<<a << "=" << b <<endl;
    else cout<< a << "<" <<b <<endl;
}
\end{lstlisting}
%\end{frame}

\begin{frame}[fragile]{include：建立自己的函数库}
\lstset{firstnumber = last}
可以在当前文件夹下，建立一个 library.cpp 文件，其中包括如下内容：
\begin{lstlisting}
void compare(int a, int b){ // 函数不返回任何值，所以类型为 void
    cout<<" Conclusion: ";
    if(a>b)cout<<a << ">" << b <<endl;
    else if(a==b)cout<<a << "=" << b <<endl;
    else cout<< a << "<" <<b <<endl;
}
\end{lstlisting}
然后建立另一个 main.cpp 文件，其中包括如下内容：
\begin{lstlisting}
#include<iostream>
using namespace std;
#include"library.cpp" // 包括 library.cpp 中的所有内容
int main(){
    int a,b;
    cout<<" Please input two integers:"<<endl;
    cout<<" a="; cin>>a;
    cout<<" b="; cin>>b;
    compare(a,b);//调用 compare 函数
    return 0;
}
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]{include：建立自己的函数库}

\begin{itemize}
\item 库文件可以按主题命名，比如所有矩阵运算函数放在一个文件里，这个文件命名为 matrix.cpp
\item 库文件可以被不同的文件 include，反复使用
\item 库文件需要认真维护
\item 在这个思路下，网上有很多现成的库可供下载调用，比如矩阵运算的 lapack, blas 等等。
\end{itemize}

\end{frame}

\iffalse
\begin{frame}[fragile]{变量的作用域}
\begin{itemize}
\item 作用域有限的叫做{\bf　局域变量}，在全局定义的叫做{\bf 全局变量}。
\item 如果变量定义在函数体中，它的作用域就是定义处到函数体结束，出了函数体以后，就无法调用这些变量了。
\item 如果变量定义在for循环中，作用域即这个for循环，所以下面的程序无法编译通过。
\end{itemize}
\begin{lstlisting}
#include<iostream>
using namespace std;

int main(){
    for(int i=0;i<1;i++)
        i;
    cout<<"i="<<i<<endl;
    return 0;
}
\end{lstlisting}
\end{frame}
\fi

\begin{frame}[fragile]{指针}
指针是一种特别的数据类型，它存放的是内存的物理地址。
\begin{lstlisting}
int a=3;
int * b;
b = & a;
cout<<" originally a="<<a<<endl;
*b +=3;
cout<<" later a="<<a<<endl;
\end{lstlisting}
第１行：定义了整型变量a，其初值为3。\\
第２行：定义整型指针（可以定义不同类型的指针）b。\\
第３行：\&是取地址符，用a的内存地址给b赋值，也就是说，让指针b指向变量a。\\
第４行：输出a的值。\\
第５行：*b表示指针b指向的内存单元，这一行让这块内存单元的值增加3，所以变量a的值也改变了。\\
第６行：输出a的值。
\end{frame}

\begin{frame}[fragile]{指针}
输出的结果为
\begin{lstlisting}
 originally a=3
 later a=6
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]{动态内存}
静态内存：编译阶段就决定了分配多大的内存。\\
动态内存：运行时才决定分配多大的内存。
\begin{lstlisting}
int n;
cout<<"n="; cin>>n;//注意这里n必须是正整数，否则下一行将会报错
int *a = new int [n];
delete [] a;
\end{lstlisting}
第1行：定义正整数n。\\
第2行：输入n的值。\\
第3行：开辟n个整数的内存，后面可以任意使用和修改这n个数。\\
第4行：释放动态内存。防止“僵尸内存”。
\end{frame}

\begin{frame}[fragile]{课堂作业(1)：定义动态矢量}

用户给定正整数$n$值，定义一个$n \times 1$的矢量 $\vec{b} = (1,1,\cdots)^\top$，即$b_i = 1, i=0,\cdots, n-1$，并输出到屏幕。

\end{frame}

\iffalse
\begin{frame}[fragile]{动态内存}
下面就是一个用动态内存的程序，自动给任意多个数排序。
\begin{lstlisting}
#include<iostream>
using namespace std;
int main(){
        int n;
        int i,j,k;
        cout<<" How many integers are to be sorted?\n n=";
        cin>>n;
        int *a = new int [n];//开辟动态内存
        for(i=0;i<n;i++){
                cout<<" a["<<i<<"]="; cin>>a[i];
        }
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]{动态内存}
\lstset{firstnumber = last}
\begin{lstlisting}
        for(i=n-1;i>=1;i--){
                for(j=0;j<i;j++){ // 将 a[0] ~ a[i] 中的最大值，放到第 i+1 个位>置 
                        if(a[j]>a[j+1]){
                                k=a[j]; // 交换 a[j] 和 a[j+1]
                                a[j]=a[j+1];
                                a[j+1]=k;
                        }
                }
        }
        cout<<" The "<<n<<" numbers after sorting: "<<endl;
        for(i=0;i<n;i++){
                cout<<a[i]<<",";
        }
        cout<<endl;
        delete [] a;//释放动态内存
        return 0;
}
\end{lstlisting}
\end{frame}
\fi

\begin{frame}[fragile]{多维数组}
\begin{lstlisting}
#include<iostream>
using namespace std;
int main(){
        int n;
        double **A = new double * [n];　//A为指向指针的指针
        for(int i=0;i<n;i++){
            A[i] = new double [n]; //A[i]为指针
            for(int j=0;j<n;j++){//给第i行赋值
                if(j!=i) A[i][j]=1;
                else A[i][j]=0;
            }
        }
        for(int i=0;i<n;i++){//释放动态内存
            delete [] A[i];
        }
        delete [] A;
        return 0;
}
\end{lstlisting}
类似地，可以定义$n$维数组。
\end{frame}

\iffalse
\begin{frame}[fragile]{课堂作业：矩阵乘以矢量}

用户给定正整数$n$值，定义一个$ n \times n$的矩阵A,令$A_{ij} = i， i,j=0,\cdots,n-1$，一个$n \times 1$的矢量 $\vec{b} = (1,1,\cdots)^\top$，即$b_i = 1, i=0,\cdots, n-1$，计算$A \vec{b}$的结果，并输出到屏幕。

\end{frame}
\fi

\begin{frame}[fragile]{内存地址顺序}
在上面定义的矩阵A中，其矩阵元的内存地址顺序为：
\begin{equation}
A[0][0], \cdots A[0][n-1], A[1][0], A[1][1], \cdots, A[1][n-1], \cdots
\end{equation}

%利用这个信息，我们可以让程序少做内存的跨越，让程序更高效。
\end{frame}

\begin{frame}{gnuplot}

\begin{figure}
\centering
\includegraphics[width=0.7\linewidth]{gnuplot_homepage}
\caption{}
\label{fig:gnuplothomepage}
\end{figure}

\begin{itemize}
\item 命令行进行交互式/脚本式操作，熟练以后操作很快。
\item 与latex无缝连接，图文结合。
\item 功能强大，可以制作3d图、动画gif文件等。
\end{itemize}
\end{frame}

\begin{frame}[fragile]{安装运行}
\begin{itemize}
\item 免费下载gnuplot安装文件\footnote{http://gnuplot.sourceforge.net/download.html}。
\item 以管理员权限运行下载的exe文件，一路按提示安装即可。
\item 安装完成以后，桌面会出现一个gnuplot图标，叫做“gnuplot..."，双击即可运行gnuplot。
\end{itemize}
\end{frame}

\begin{frame}[fragile]{第一张图片}
gnuplot窗口中会出现提示符
\begin{lstlisting}
gnuplot>
\end{lstlisting}
在提示符下输入如下内容并回车，
\begin{lstlisting}
gnuplot>plot x*x with line
\end{lstlisting}
就会弹出一张图片，画着抛物线$y=x^2$。

plot和splot是gnuplot的基本命令，后面的x*x是函数，也可以改成sin(x),cos(x),exp(x)等等，gnuplot内置了这些常用的函数，幂次可以用$x**2,x**3$等表达。

with line是值用曲线作图，你可以试试with point。
\end{frame}

\begin{frame}[fragile]{修改图例}
我们可以让它显示x、y坐标轴标记，并修改曲线标记：
\begin{lstlisting}
gnuplot>set xlabel "x"
gnuplot>set ylabel "y"
gnuplot>plot x*x with line title "f(x)=x^2"
\end{lstlisting}
set xlabel "xxx"即将x轴名字标为xxx，set ylabel类似，而title后面双引号内则是曲线的标记内容。

在窗口的上端，有"export plot to file"的快捷键，存为png文件即可。
\end{frame}

\begin{frame}[fragile]{输出到文件}
我们也可以改变输出方式，让它自动生成一个文件，如下
\begin{lstlisting}
gnuplot>set terminal png
gnuplot>set output "1stGraph.png"
gnuplot>set xlabel "x"
gnuplot>set ylabel "y"
gnuplot>plot x*x with line title "f(x)=x^2"
\end{lstlisting}
terminal即终端，在这里表示输出的途径，terminal默认的是pop，即弹出图片。
现在我们把它设为png，即生成png文件，但我们还需要set output命令来指定文件名。
\end{frame}

\begin{frame}[fragile]{脚本驱动}
我们也可以将这些命令写成一个脚本，并自动生成png、eps、ps等文件。
新建文本文档"1stGraph.txt"，其中内容为
\begin{lstlisting}
set terminal png
set output "1stGraph.png"
set xlabel "x"
set ylabel "y"
plot x*x with line title "f(x)=x^2"
\end{lstlisting}
然后在脚本所在文件夹下运行gnuplot，或点击 File -> Change directory ...，改变程序运行路径，然后在gnuplot窗口中打入
\begin{lstlisting}
gnuplot>load "1stGraph.txt"
\end{lstlisting}
就会自动执行1stGraph.txt脚本，生成1stGraph.png文件。
\end{frame}

\iffalse
\begin{frame}[fragile]{latex插入图片}
我们可以在latex中包括这个png文件，latex代码为
\begin{lstlisting}{language=tex}
\begin{figure}[h]
\centering
\includegraphics[width=0.7\linewidth]{1stGraph}
\caption{gnuplot:第一张图}
\label{fig:1stGraph}
\end{figure}
\end{lstlisting}
\begin{figure}[h]
\centering
\includegraphics[width=0.6\textwidth]{1stGraph}
\label{fig:1stGraph}
\end{figure}
\end{frame}

\begin{frame}[fragile]{散点图、折线图}
如果有一个呈两列的数据文件"ScatterDiagram\_LineChart.txt"，其中内容如下
\begin{lstlisting}
-10     2
-8      3
-6      1
-4      -1
-2      4
\end{lstlisting}
那么我们可以写一个脚本，让它自动生成散点图、折线图。
\end{frame}

\begin{frame}[fragile]{散点图、折线图}
\begin{lstlisting}
set terminal cairolatex size 4 inch, 2.4 inch
set output "ScatterDiagram_LineChart.tex"
set xlabel 'log$_{10}(h)$'
set ylabel '$\epsilon = \int^\infty_1 f(x) dx $'
plot "ScatterDiagram_LineChart.txt" title "折线图" w l, "ScatterDiagram_LineChart.txt" title "散点图" w p　pt 7
\end{lstlisting}
\begin{itemize}
\item cairolatex是terminal的一种选项，它生成tex文件，其中包含了图片与图例部分。
\item size 4inch, 2.4inch　表示生成图片的尺寸
\item 在set xlabel，set ylabel中我们展示了latex公式编写。
\item plot命令中，w l是with line的缩写, w p是with point/points缩写。
\item plot命令后面可以跟两条画图命令，用逗号隔开，两图显示在一起。\\
\item pt 7　表示pointtype 7，即用内置的第7种点作图。\\
\item 如果想知道内置的点都是什么样的，可以在gnuplot中打test
\end{itemize}
\end{frame}

\begin{frame}[fragile]{散点图、折线图}

注意，如果gnuplot的运行目录，与数据文件不在同一个地方，可能会报错。
这时可以使用gnuplot的上方第四个小图标“change directory”，找到数据文件所在文件夹，即可。

用gnuplot运行上述脚本以后，会生成相应的tex文件，可以在latex中包括这个tex文件，如下生成图片
\begin{lstlisting}{language=tex}
\begin{figure}[h]
\centering
%\includegraphics[width=0.7\linewidth]{ScatterDiagram_LineChart}
\input{ScatterDiagram_LineChart.tex}
\caption{gnuplot:散点图与折线图，x轴与y轴的图例没有任何意义，只是为了展示latex的公式编辑。}
\label{fig:ScatterDiagram_LineChart}
\end{figure}
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]{散点图、折线图}
\begin{figure}[h]
\centering
%\includegraphics[width=0.7\linewidth]{ScatterDiagram_LineChart}
\input{ScatterDiagram_LineChart.tex}
\caption{gnuplot:散点图与折线图，x轴与y轴的图例没有任何意义，只是为了展示latex的公式编辑。}
\label{fig:ScatterDiagram_LineChart}
\end{figure}
\end{frame}
\fi

\begin{frame}[fragile]{gif文件：动图}
gnuplot的terminal可以有很多选项，其中gif包括animate动画选项。

下面是一个正弦波波形图脚本：
\begin{lstlisting}
set terminal gif animate
set output "sinx.gif"
set xrange [0:4*pi]
set yrange [-1:1]
do for [i=0:80]{
        plot sin(x+i*pi/40) linewidth 3 title sprintf("t=%d s",i)
}
\end{lstlisting}
其中set xrange约定x轴范围，而do for循环生成81桢，这81桢自动生成gif文件。
\end{frame}

\begin{frame}[fragile]{参数图}
如果想画圆，可以用参数坐标
\begin{eqnarray}
x &=& \cos t,\\
y &=& \sin t.
\end{eqnarray}
以t为变量，自动画出一个圆。
用如下脚本
\begin{lstlisting}
set term png
set output "circle.png"
set parametric
set dummy t
set trange [-pi:pi]
plot cos(t), sin(t) with line linewidth 3
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]{参数图}
\begin{figure}[h]
\centering
\input{circle.tex}
\caption{gnuplot:参数图。}
\label{figure:circle}
\end{figure}
\end{frame}

\begin{frame}[fragile]{三维图}
plot命令用于画二维图，而splot可以画三维图。
比如，我们可以画出$f(x,y)=10x^2 + y^3$的曲面图
\begin{lstlisting}
f(x,y)=10*x**2 + y**3
set isosamples 100
splot f(x,y) title "$z=10x^2+y^3$"
\end{lstlisting}
其中，f(x,y)=10*x**2 + y**3定义了一个函数，也就是说gnuplot可以自由定义函数。
set isosamples 100 是给出网格密度。
\end{frame}

\begin{frame}[fragile]{三维图：颜料板、打光}
plot命令用于画二维图，而splot可以画三维图。
比如，我们可以画出$f(x,y)=10x^2 + y^3$的曲面图
\begin{lstlisting}
f(x,y)=10*x**2 + y**3
set isosamples 100
set palette rgbformulae 8,9,7
splot f(x,y) title "z=10x^2+y^3" with pm3d
\end{lstlisting}
其中，f(x,y)=10*x**2 + y**3定义了一个函数，也就是说gnuplot可以自由定义函数。
set isosamples 100 是给出网格密度。

如果需要打光，可以在$splot$命令上方再加入一行
\begin{lstlisting}
set pm3d lighting primary 0.5 specular 0.2
\end{lstlisting}
\end{frame}



\begin{frame}[fragile]{三维图}
\begin{figure}[h]
\centering
\includegraphics[width= 0.7 \textwidth]{3d_surface}
\caption{三维曲面图：颜料板上色、灯光}
\label{fig:3dsurface}
\end{figure}
\end{frame}

\iffalse
\begin{frame}[fragile]{上色、灯光}
如果做的更加复杂一点，可以画出三维几何体，并给它上色，打上灯光。
下面的例子来自官网demo。
\begin{lstlisting}
set terminal cairolatex color size 4, 3
set output '3d_lighting.tex'
unset border
unset key       #unset the title
#set style fill   solid 1.00 noborder # set style fill density = 1.00
set dummy u, v  #independent variables
set object  1 rect from screen 0, 0 to screen 1, 1
set object  1 behind lw 1.0  dashtype solid fc  rgb "gray"  fillstyle   solid 1.00 border lt -1 #set background color-filling
set parametric # from normal functions to parametric functions
set view 236, 339, 1.245, 1 #set the view angle: rot_x, rot_z, scale, scale_z
set isosamples 75, 75
unset xtics
unset ytics
unset ztics
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]{上色、灯光}
\lstset{firstnumber = last}
\begin{lstlisting}
set title "PM3D surfaces with specular highlighting"
set urange [-pi,pi]
set vrange [-pi,pi]
set pm3d depthorder
set pm3d lighting primary 0.5 specular 0.6
set palette rgbformulae 8, 9, 7
splot cos(u)+.5*cos(u)*cos(v),sin(u)+.5*sin(u)*cos(v),.5*sin(v) with pm3d,     1+cos(u)+.5*cos(u)*cos(v),.5*sin(v),sin(u)+.5*sin(u)*cos(v) with pm3d
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]{上色、灯光}
\begin{itemize}
\item unset border, unset xtics等等，表示取消边框、xyz轴数字，unset key表示取消图例。
\item set dummy u,v表示u,v为自有参数。
\item set object两行定义的是正方形灰色背景。
\item set isosamples 75,75决定的是线的稠密度，如果稠密度比较低，画出来的更像多面体。
\item set pm3d depthorder表示离观察者更近的线条会挡住后面的线条，这样才会产生立体感。
\item set pm3d lighting primary 0.5 specular 0.6表示打上灯光，光强为0.5（最大值为1），而高亮效果的强度为0.6（最大值为0.6）。
\item set palette rgbformulae 8,9,7定制调色板，即确定颜色填充方案，如果改动数字，会得到不同的颜色填充效果，但是不是任何方案都好看。。。\\
\item 最后一行splot将两个参数图画在同一张图上，是两个嵌套的环状体。
\end{itemize}
\end{frame}

\begin{frame}[fragile]{上色、灯光}
\begin{figure}[h]
\centering
\input{3d_lighting.tex}
%\caption{三维图:背景为灰色色块，两个环状体由两个参数图实现，上色、灯光由palette, pm3d lighing实现。}
\label{figure:3d_lighting}
\end{figure}
\end{frame}
\fi

\begin{frame}{gnuplot help}
\begin{itemize}
\item 在gnuplot界面中打入help，即可调出help文档，也可以打入help xxx，比如help plot，就会弹出plot相关的说明。
\item 在c:$\backslash$Program Files$\backslash$gnuplot$\backslash$docs中有手册，可供查阅。
\item gnuplot官网\footnote{http://www.gnuplot.info}上有一些链接与教程。
\end{itemize}
\end{frame}


\begin{frame}[fragile]{作业}
1. (1)请参考百度词条“利萨如图形”,并用gnuplot做出任意一个利萨如图形，并输出到一个png文件。（要求提交gnuplot脚本，并说明你的利萨如图形的方程。提示：gnuplot脚本中，＃后面的内容表示注释。）
(2)* 画一个小球，让它在利萨如曲线上运动，形成一个动图。

\iffalse
4. 如果我们需要做求和，
\begin{equation}
s_{up} = \sum^N_{n=1} 1/n,
\end{equation}
我们可以按上式的顺序求和，也可以用逆序求和
\begin{equation}
s_{down} = \sum^1_{n=N} 1/n,
\end{equation}
１）请问哪一种方式更精确？\\
２）编写程序，计算 $log_{10} | (s_{up} (N) - s_{down} (N) )/ s_{down} (N) |$，$N=10,100,1000,...,10^{10}$。
将这10组数据输出到文件。
３）用上面的数据，在gnuplot中画出折线图，用 terminal ps，输出到一个ps文件。
\fi
\end{frame}

\begin{frame}
\frametitle{目录}
	\begin{itemize}
		\item { 第一章：前言 \hspace{0.2cm} }
		\vspace{1cm}
		\item 第二章：计算语言、工具与误差
		\vspace{1cm}
		\item {\color{blue}第三章：数值误差 }
	\end{itemize}
\end{frame}

\begin{frame}{整数的表达}

\begin{itemize}
%\item [1] 计算机能表达的数的个数是有限的。
\item 人类的十进制是一个偶然，十进制的整数表示为：
\begin{equation}
	a_0 10^0 + a_1 10^1 + \cdots + a_n 10^n
\end{equation}
问：十进制的小数是怎样表达的？
\item 计算机使用2进制，一个数位取值0和1，对应晶体管的两种状态。2进制的整数表示为：
\begin{equation}
	a_0 2^0 + a_1 2^1 + \cdots + a_n 2^n
\end{equation}
问：2进制的小数怎样表达？
\end{itemize}
\end{frame}

\begin{frame}{单精度浮点数的表达}
\begin{itemize}
\item 2进制的科学计数法：
\begin{equation}
	(-1)^s 0. a_{-1} a_{-2} a_{-3} ... a_{-23} 2^{exponent},
\end{equation}
其中，s 占一个 bit，exponent 占 8 个 bit，所以数值部分占 23 个bit（一共32位）。
\item 计算机只能表示一系列离散的数。
\item 赋值的故事：如果你将值 x 赋给变量 a，x 无法用上面的形式严格表出，那么计算机会在自己能表达的数中，取一个离 x 最近的数，我们将它记作 $fl(x)$（$fl$ 是 float 的缩写），赋值给 a，所以实际上发生的是：
\begin{equation}
	a = fl (x),
\end{equation}
\end{itemize}
\end{frame}

\begin{frame}{单精度浮点数的表达}
\begin{itemize}
\item $fl (x)$ 相对 x 的相对误差的绝对值为
\begin{equation}
	| \frac{ fl (x) - x }{ fl (x) } | \approx 2^{-23} \approx 10^{-7}
\end{equation}
\item 类似地，双精度数的相对误差约为 $10^{-16}$。这叫做 {\bf round off error}，翻译为 舍入误差。
\end{itemize}

\end{frame}

\begin{frame}{两个相近的数相减}
我们说了，$x$ 在计算机中实际上是 $fl(x)$，那么，如果我们要计算两个双精度数的差 $a = b - c$，则实际上发生的是
\begin{equation}
	fl(a) = fl(b) - fl(c),
\end{equation}
它并不是真的 $a$ 的值，我们自然会关心，误差有多大。
相对误差为
\begin{equation}
	\frac{fl(a)}{a} -1 = \frac{ fl(b) - fl(c) }{ a} -1 = \frac{ b (1+ \epsilon_b) - c(1+\epsilon_c) }{a}
	-1= \frac{ b \epsilon_b - c \epsilon_c }{a},
\end{equation}
其中，$\epsilon_b, \epsilon_c$ 是 $fl(b), fl(c)$ 的相对误差，都是 $10^{-16}$ 量级
如果 $ b \approx c$，我们可以将上式近似为
\begin{equation}
	\frac{ fl(a) }{a} -1= \frac{ b \epsilon_b - c \epsilon_c }{a} \approx \frac{c}{a}(\epsilon_b - \epsilon_c),
\end{equation}
$\epsilon_b, \epsilon_c$ 都是 $2^{-23}$ 数量级，所以它俩的差也约为 $10^{-16}$。
\end{frame}

\begin{frame}{两个相近的数相减}
所以对于双精度数，如果 $ a= b-c << c$，相对误差的上限约为
\begin{equation}
	\frac{ fl(a) }{a} -1 \leq \frac{c}{a} 10^{-16}
\end{equation}
相应地，误差的上限约为
\begin{equation}
	fl(a) - a \leq c 10^{-16}
\end{equation}
这个误差有可能超过 $a$，就完全失去了精度，计算失去了意义。

如果用单精度浮点数，上面的 $10^{-16}$ 就变成 $10^{-7}$，所以会更加糟糕。
所以在本课程中，我们一律用 double 而不用 float。
\end{frame}

\begin{frame}[fragile]{两个相近的数相减}
我们做一个超级简单的例子，让 10000.1 减去 10000，然后命令计算机，输出结果的前 15 位有效数字。
\begin{lstlisting}
#include<iostream>
#include<iomanip> // 带上这个库，我们就可以用 setprecision 指定输出的精度
using namespace std;

int main(){

    double a = 10000.1, b = 10000;
    double c = a - b;
    cout<<" relative error = "<<setprecision(15)<< c/0.1 -1<<endl; // c 的理论值为 0.1， 所以 c/0.1 -1 就是相对误差
    // setprecision(15)指定输出 15 位有效数字

    return 0;
}
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]{两个相近的数相减}
运行以后，会得到
\begin{lstlisting}
    relative error = 3.63797880709171e-12,
\end{lstlisting}
注意，c++　中　$e-12$　或　$E-12$ 是指 $10^{-12}$。
根据我们上面的理论分析，相对误差的上限约为
\begin{equation}
	\frac{ 10000 }{0.1} 10^{-16} = 10^{-11},
\end{equation}
所以结果与我们的理论预测可以认为是一致的。
你可以试着改动这个程序，将 a,b 中的 0 多加几个，观察程序输出的相对误差。
0加的足够多以后，相对误差就会接近１，甚至超过１，也就是说，计算完全失去了意义。

\end{frame}

\begin{frame}{舍入误差}

\begin{itemize}
\item [1] {\bf 大数相减}：永远警惕两个非常接近的数相减，舍入误差可能比理论值还要大！
\item [2] {\bf 大数加(减)小数}：如果你将两个数量级差别很大的数相加，舍入误差可能比很小的那个数还要大(underflow)。
\item [3] 在迭代算法中注意舍入误差被放大(作业)。
\end{itemize}

一方面，我们尽量用双精度浮点数，即　double；另一方面，我们设计算法的时候，需要了解上述问题。

\vspace{1cm}

%没有一个固定的咒语，可以杀死舍入误差，我们只能主动去注意这个问题。。。

\end{frame}

\begin{frame}{作业：迭代算法中的舍入误差}
欲计算积分
\begin{equation}
E_n = \int^1_0 x^n e^{x-1} dx,
\end{equation}
可以构造迭代式
\begin{equation}
E_n =  \int^1_0 x^n e^{x-1} dx,
\end{equation}
容易证明
\begin{equation}
E_0 = 1 - \frac{1}{e}, ~~~~~ E_{n} = 1 - n E_{n-1}.
\end{equation}
右边的式子可以用分部积分证明。

1) 从$E_0$出发，用上面的递推公式计算 $E_{20}$。
\end{frame}

\begin{frame}{作业：迭代算法中的舍入误差}
2) 将递推式改写为
\begin{equation}
E_{n-1} = \frac{ 1 - E_n }{n},
\end{equation}
然后假设 $E_{30}=0$ (这里当然会引入误差)，用上面的递推式推算 $E_{20}$。

\vspace{0.5cm}

3) 分析上面两种算法中的舍入误差，并做自己的判断(可参考马红儒老师的讲义P10 - P11)。
\end{frame}

\iffalse
\begin{frame}[fragile]{作业}


1. 在　c++　中，求余运算符号为　\%，例子：
\begin{lstlisting}
    a = 3%2;
\end{lstlisting}
即用 3　除以　2　得到的余数，即　１　赋值　ａ。
请用我们讲的知识，编写程序，完成以下任务
\begin{itemize}
\item 要求用户输入两个正整数 a,b
\item 在屏幕上输出　a 除以　b 的余数。
\end{itemize}


\vspace{1cm}

1. 质数的定义为：只能被1和自己整除的正整数。编写程序输出100以内的所有质数。

\vspace{1cm}


2. 编写程序，完成如下任务：\\
\begin{itemize}
\item 要求用户输入 7 个浮点数
\item 自动从大到小排序，并输出到屏幕
\end{itemize}

\end{frame}
\fi

\iffalse
\begin{frame}[fragile]{作业}

**4. $e^x$　可以做泰勒展开
\begin{equation}
	e^x = \sum^\infty_{n=0} \frac{x^n}{n!},
\end{equation}
可以指定当　$ |x^N / N!| < \epsilon$　（$\epsilon$　是一个很小的数，比如，可以取　$\epsilon = 10^{-6}$）时，将前面　$N$　项的和作为　$e^x$　的近似：
\begin{equation}
	e^x \approx \sum^{N-1}_{n=0} \frac{x^n}{n!},
\end{equation} 
\end{frame}
\fi

\iffalse
\begin{frame}[fragile]{作业}
也可以将求和顺序反过来
\begin{equation}
	e^x \approx \sum^{0}_{n=N-1} \frac{x^n}{n!},
\end{equation} 
请问哪一种算法可以更有效地避免舍入误差的影响，得到更好的精度？
试编程，分别用这两种算法计算　$e$　的值。\\
\vspace{1cm}
提示：c++　中如果包括　cmath 包，即
\begin{lstlisting}
    #include<cmath>
\end{lstlisting}
即可在代码中调用　e 指数函数，即　exp(１)　表示　$e^１$，作为精确值，与上面的两种算法的计算结果相比较。
\end{frame}
\fi



\end{document}


\begin{frame}{算法}
所谓算法，就是一系列有序的动作，完成一个特定的任务。

下面是我的青椒炒肉丝算法：
\begin{itemize}
\item 先去超市买菜，
\item 再切青椒、肉丝，用酱油、料酒、姜丝、盐腌肉丝一刻钟，
\item 大火放油炒青椒（加少量水）到青椒稍微有一点软，
\item 大火放油炒肉丝，肉丝都发白时加入青椒，
\item 继续炒几分钟然后放生抽（上色）和少量盐，
\item 炒匀以后马上装盘放上餐桌。
\end{itemize}
它定义了一系列有序的动作（买菜、备料、炒菜等一系列细节），来完成特定的任务：做出青椒炒肉丝这盘菜。
\end{frame}

\begin{frame}{排序算法：冒泡法}
下面我们接触第一个数值算法，即冒泡法排序。
我们的任务是，给定任意 5 个不同的整数 $a_1, a_2, \cdots, a_5$，写一个程序对它们进行自动排序，并按从小到大的顺序输出。
冒泡法的步骤如下
\begin{itemize}
	\item [1] 比较 $a_1, a_2$，如果 $a_1 > a_2$，就将它们调换。
	\item [2] 比较 $a_2, a_3$, 如果 $a_2 > a_3$，如果 $a_2 > a_3$ 就将他们调换。
	注意这里的 $a_2$ 只是指第 2 个数，它不一定等于步骤 1 中的 $a_2$ 了。
	\item [3] ...
	\item [4] 比较 $a_4, a_5$，如果不是从小到大，就调换。
	\item [5] 重复步骤 1-3
	\item [6] 重复步骤 1-2
	\item [7] 重复步骤 1
\end{itemize}
步骤 1-4 实现了一件事：将最大的数放到最末尾；
步骤 5 则将第二大的数放到次末尾；
步骤 6 将第三大的数放到了倒数第三位；
步骤 7 将第四大的数放到了倒数第四位；
任务完成，输出结果。
\end{frame}

\begin{frame}[fragile]{排序算法：冒泡法}
这些步骤，可以用两层嵌套的 for 语句来实现：
\begin{lstlisting}
#include<iostream>
using namespace std;
int main(){
    int a[5] = { 1,8,9,5,3};//待排序的数字
    int i,j,k;// 声明变量
    for(i=4;i>=1;i--){
        for(j=0;j<i;j++){ // 将 a[0] ~ a[i] 中的最大值，放到第 i+1 个位置 
            if(a[j]>a[j+1]){
                k=a[j]; // 交换 a[j] 和 a[j+1]
                a[j]=a[j+1];
                a[j+1]=k;
            }
        }
    }
    cout<<" The five numbers after sorting: "<<endl;
    for(i=0;i<5;i++)
        cout<<a[i]<<",";
    cout<<endl;
    return 0;
}
\end{lstlisting}
\end{frame}

